การเพิ่มประสิทธิภาพแบบเว้า: พื้นฐานทางเรขาคณิตของการเพิ่มประสิทธิภาพแบบเว้า

จินตนาการถึงการเดินทางผ่านภูมิประเทศที่ซับซ้อน ซึ่งเป้าหมายของคุณคือการหาจุดที่ใกล้เคียงกับความปลอดภัยที่สุด ในภาษาของการเพิ่มประสิทธิภาพ ความปลอดภัยนี้คือเซต $C$ และการหาจุดที่ใกล้ที่สุดคือ การฉายภาพ. แม้ว่าแนวโน้มของเหตุผลจะบ่งบอกว่าจะมีจุดที่ใกล้ที่สุดเพียงจุดเดียวเสมอไป แต่ความจริงทางคณิตศาสตร์กลับซับซ้อนกว่านั้น พื้นฐานทางเรขาคณิตของการเพิ่มประสิทธิภาพแบบเว้าอยู่บนการกำหนดความใกล้ชิดอย่างเป็นระบบ ซึ่งข้ามความเข้าใจเชิงยูคลิดมาสู่การแทนที่เชิงฟังก์ชันที่เข้มงวด เช่น ฟังก์ชันตัวบ่งชี้และฟังก์ชันสนับสนุน

1. การฉายภาพและการวัดระยะห่าง

ระยะห่างจากจุด $x_0$ ไปยังเซต $C$ ถูกนิยามว่าเป็นค่าต่ำสุดของระยะห่างทั้งหมดไปยังจุดในเซต:

$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$

ตัวดำเนินการที่ทำให้ได้ระยะห่างนี้คือตัวดำเนินการฉายภาพ:

$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$

สำหรับไฮเปอร์พลาเนทที่เรียบง่ายที่นิยามโดย $a^T x = b$ การฉายภาพมีคำตอบรูปแบบปิดที่สวยงาม: $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$ แต่สำหรับเซตทั่วไป ปัญหานี้ยังคงเป็นปัญหาการเพิ่มประสิทธิภาพภายใต้เงื่อนไขจำกัด: ลดค่า $\|x - x_0\|$ โดยมีเงื่อนไข $f_i(x) \leq 0$ และ $Ax = b$.

2. เรขาคณิตเชิงฟังก์ชัน

เพื่อจัดการข้อจำกัดทางเรขาคณิตเป็นองค์ประกอบหลักในการเพิ่มประสิทธิภาพ เราใช้ฟังก์ชัน 'กระจกเงา' สองชนิดที่ทรงพลัง:

ฟังก์ชันตัวบ่งชี้ $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. ฟังก์ชันนี้ทำให้เรขาคณิตกลายเป็นค่าปรับเชิงตัวเลข
ฟังก์ชันสนับสนุน $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. ฟังก์ชันนี้อธิบายเซตโดยใช้ไฮเปอร์พลาเนทขอบเขตในทุกทิศทาง

ทฤษฎีบท: ทฤษฎีบทของโมตซ์กิน

เซต $C \in \mathbf{R}^n$ ที่ไม่ว่างเปล่าและปิด เป็น เซตเชเบเชฟ (มีการฉายภาพที่ไม่ซ้ำกันสำหรับทุก $x_0$) ก็ต่อเมื่อมันเป็น เว้า.

การพิสูจน์แบบสรุป (ความไม่ซ้ำกัน)

สมมุติว่า $C$ เป็นเว้า และนอร์มเป็นเว้าอย่างเข้มงวด หากมีจุดที่ใกล้ที่สุดสองจุดที่แตกต่างกัน $u, v \in C$ ที่มี $\|u - x_0\| = \|v - x_0\| = d$ แล้วจุดกึ่งกลาง $w = (u+v)/2$ จะอยู่ใน $C$ (ตามความเป็นเว้า)

จากความเป็นเว้าอย่างเข้มงวดของนอร์ม: $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$

สิ่งนี้ขัดแย้งกับสมมุติฐานที่ว่า $d$ เป็นระยะห่างต่ำสุด ดังนั้นการฉายภาพต้องเป็นเพียงจุดเดียวเท่านั้น

คำเตือน 8.4: ความพึ่งพาต่อนอร์ม

เราพบว่ามักจะสร้างไฮเปอร์พลาเนทแยกออกโดยใช้: $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$ ระวัง! การสร้างแบบเฉพาะนี้ถูกต้อง เฉพาะสำหรับนอร์มยูคลิด. นอร์มทั่วไปต้องการการจัดการความตั้งฉากอย่างละเอียดมากขึ้น

🎯 ข้อคิดสำคัญ

ความเป็นเว้าคือ 'กาว' ที่ทำให้มั่นคงในการเพิ่มประสิทธิภาพทางเรขาคณิต หากขาดความเป็นเว้า งานที่เรียบง่ายอย่าง 'การหาจุดที่ใกล้ที่สุด' อาจนำไปสู่คำตอบหลายชุดที่ขัดแย้งกัน ส่งผลให้เกิดความไม่มั่นคงในอัลกอริธึม

คำถามที่ 1

ตามทฤษฎีบทของโมตซ์กิน สิ่งจำเป็นและเพียงพอสำหรับเซตที่ไม่ว่างเปล่าและปิดใน $\mathbf{R}^n$ เพื่อเป็นเซตเชเบเชฟคืออะไร?

มันต้องมีขอบเขตและเปิด

มันต้องเป็นเว้า

มันต้องมีจุดกำเนิด

มันต้องเป็นส่วนย่อย

คำถามที่ 2

ค่าคำตอบรูปแบบปิดสำหรับการฉายภาพจุด $x_0$ ไปยังไฮเปอร์พลาเนท $a^T x = b$ ในพื้นที่ยูคลิดคืออะไร?

P_C(x₀) = x₀ + (b - aᵀx₀)a / ||a||₂²

P_C(x₀) = x₀ - (b + aᵀx₀)a / ||a||₂

P_C(x₀) = (b / aᵀx₀)a

P_C(x₀) = x₀ + aᵀx₀ / b

คำถามที่ 3

ทำไมการฉายภาพไปยังเซตของเมทริกซ์ลำดับ $k$ (ตัวอย่าง 8.2) จึงอาจไม่มีความไม่ซ้ำกันได้?

เซตไม่เป็นเว้า

เซตไม่ปิด

ลำดับเป็นคุณสมบัติเชิงเส้นเสมอ

เมทริกซ์ไม่มีนอร์ม

คำถามที่ 4

ฟังก์ชันใดช่วยให้เราแสดงเซต $C$ เป็นค่าปรับในฟังก์ชันวัตถุประสงค์ โดยให้ค่า 0 หากจุดอยู่ในเซต และ ∞ ถ้าไม่อยู่?

ฟังก์ชันสนับสนุน $S_C(x)$

ฟังก์ชันตัวบ่งชี้ $I_C(x)$

ฟังก์ชันระยะห่าง $\text{dist}(x, C)$

เมทริกซ์กรัม

คำถามที่ 5

จริงหรือเท็จ: การสร้างไฮเปอร์พลาเนทแยกออกโดยใช้จุดกึ่งกลางระหว่าง $x_0$ และการฉายภาพของมัน ใช้ได้กับนอร์มใด ๆ หรือไม่?

จริง

เท็จ

กรณีศึกษา: การวางแผนเส้นทางของหุ่นยนต์

ข้อจำกัดทางเรขาคณิตในระบบเรียลไทม์

แขนหุ่นยนต์กำลังติดตามเป้าหมายที่ $x_0 = [0, 0]^T$ แต่ต้องหลีกเลี่ยง 'พื้นที่ห้ามเข้า' ที่กำหนดโดยขอบเขตที่ไม่เป็นเว้าของสี่เหลี่ยมจัตุรัสหนึ่งหน่วย: $C = \{x \in \mathbf{R}^2 \mid \|x\|_\infty = 1\}$. อัลกอริธึมควบคุมพยายามหาการจัดวางที่ปลอดภัยที่สุดโดยการแก้ปัญหา $\text{minimize } \|x - x_0\|$ โดยมีเงื่อนไข $x \in C$

คำถามที่ 1

ระบุการฉายภาพ $P_C(x_0)$ และอภิปรายผลกระทบต่อเสถียรภาพการควบคุมของหุ่นยนต์

คำตอบ:
สำหรับ $x_0 = 0$ และ $C$ เป็นเส้นขอบของสี่เหลี่ยมจัตุรัสหนึ่งหน่วย มีจุดสี่จุดที่มีระยะห่างเท่ากัน: $[1, 0], [-1, 0], [0, 1], [0, -1]$ ทั้งหมดอยู่ห่างกัน $d=1$

ผลที่ตามมา: เนื่องจากเซตไม่เป็นเว้า การฉายภาพจึงไม่เป็นเอกลักษณ์ ซึ่งอาจก่อให้เกิด 'การสั่นสะเทือน' หรือความไม่มั่นคงทางอัลกอริธึม ที่ตัวควบคุมของหุ่นยนต์สลับอย่างรวดเร็วระหว่างเป้าหมายที่เหมาะสมที่สุดสี่จุด ซึ่งอาจทำลายฮาร์ดแวร์ได้

คำถามที่ 2

เราจะจัดรูปแบบการลดระยะห่างแบบ 'Y-form' สำหรับหุ่นยนต์ที่หลีกเลี่ยงพื้นที่ห้ามเข้ารูปพอลิเฮดรัล $Ax \le b$ ได้อย่างไร?

คำตอบ:
ปัญหานี้ถูกจำลองเป็น:
$$\text{minimize } \|y\|$$
$$\text{subject to } Ax \le b, \quad x_0 - x = y$$
โดยที่ $y$ แทนค่าความคลาดเคลื่อนหรือ 'เวกเตอร์ระยะห่าง' ระหว่างเป้าหมายปัจจุบัน $x_0$ และจุดที่เป็นไปได้ $x$ หากพื้นที่เป็นพอลิเฮดรัล ปัญหานี้จะกลายเป็นโปรแกรมควอดราติกมาตรฐาน (QP) สำหรับนอร์มยูคลิด